import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description:
 * 小红可以对一个数进行如下两种操作：将这个数乘以 a；
 * 或将这个数乘以 b。操作的次数是没有限制的。
 * 小红想知道，自己最少经过多少次操作以后，可以把 c 变成 d?
 * @Date:Create in 19:38  2022/7/13
 */
public class mianshi1 {

    public static void main(String[] args) {
        int a = 2, b = 3, c = 5, d = 80;
        System.out.println(min(a, b, c, d));
    }

    public static int min(int a, int b, int c, int d) {
        int count = 0;
        if (c == d) return 0;
        HashSet<Integer> hash = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        hash.add(c);
        queue.offer(c);
        while (!queue.isEmpty()) {
            int len = queue.size();
            ++count;
            for (int i = 0; i < len; ++i) {
                int cur = queue.poll();
                int get1 = cur * a, get2 = cur * b;
                if (get1 == d || get2 == d) {
                    return count;
                }
                if (!hash.contains(get1) && get1 < d) {
                    queue.offer(get1);
                    hash.add(get1);
                }
                if (!hash.contains(get2) && get2 < d) {
                    queue.offer(get2);
                    hash.add(get2);
                }
            }
        }
        return -1;
    }
}
